package com.LeeCode;

/**
 * 翻转等价二叉树
 */

public class Code951 {
    public static void main(String[] args) {
        Integer[] arr1 = {0, null, 1};
        Integer[] arr2 = {0, 1};

        TreeNode root1 = Utils.buildTree(arr1);
        TreeNode root2 = Utils.buildTree(arr2);
        System.out.println(new Code951().flipEquiv(root1, root2));
    }

    public boolean flipEquiv(TreeNode root1, TreeNode root2) {
        if (root1 == null || root2 == null) return root1 == root2;
        if (root1.val != root2.val) return false;

        // 尝试匹配左子树
        if (check(root1, root2)) {
            TreeNode temp = root1.left;
            root1.left = root1.right;
            root1.right = temp;
        }

        return flipEquiv(root1.left, root2.left) && flipEquiv(root1.right, root2.right);
    }

    private boolean check(TreeNode root1, TreeNode root2) {
        if (root1.left == null || root2.left == null)
            return root1.left != root2.left;

        return root1.left.val != root2.left.val;
    }
}
